package com.promote.algorithm;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName FindRepeatNum
 * Description 查找数组中重复的数
 * @Author LiZiHao
 * Date 2021/7/7 11:06
 * @Version 1.0
 **/
public class FindRepeatNum {

    public static void main(String[] args) {
        int[] nums = {2,3,1,0,2,5,3};
        System.out.println(findRepeatNum2(nums));
    }
    //方法一
    public static int findRepeatNum(int[] nums) {
        Set<Integer> tmp = new HashSet<>();
        for (int num : nums) {
            if (tmp.contains(num)) {
                return num;
            }
            tmp.add(num);
        }
        return -1;
    }
    //方法2
    public static int findRepeatNum1(int[] nums){
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                return nums[i];
            }
        }
        return -1;
    }
    //方法3
    public static int findRepeatNum2(int[] nums) {
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == i) continue;

            int num = nums[i]; //2
            //如果交换位置有期望值，证明重复
            if (nums[num] == num) {
                return num;
            }
            int tmp = nums[num]; //1
            nums[num] = num; //2
            nums[i] = tmp; //1
            i--;
            System.out.println(Arrays.toString(nums));
        }
        return -1;
    }
}
